(A) Field of the Invention
The invention relates to a quantum computer; that is, an array of quantum bits (called qubits). More specifically, it relates to methods for using a classical computer to generate a sequence of operations that can be used to operate a quantum computer.
(B) Description of Related Art
Henceforth, we will allude to certain references by codes. Here is a list of codes and the references they will stand for.    Ref.Har is A. W. Harrow, A. Hassidim, S. Lloyd, “Quantum algorithm for solving linear systems of equations”, arXiv:0811.3171v3    Ref.Chi is A. M. Childs, “On the relationship between continuous- and discrete-time quantum walk”, arXiv:0810.0312    Ref.Ley is S. K. Leyton, T. J. Osborne, “A quantum algorithm to solve nonlinear differential equations”, arXiv:0812.4423    Ref.She is L. Sheridan, D. Maslov, M. Mosca, “Approximating Fractional Time Quantum Evolution”, arXiv:0810.3843    Ref.Woc is P. Wocjan, C. Chiang, A. Abeyesinghe, D. Nagaj, “Quantum Speed-up for Approximating Partition Functions”, arXiv:0811.0596    Ref.Pou is D. Poulin, P. Wocjan, “Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer”, arXiv:0905.2199    Ref.Tem is K. Temme, T. J. Osborne, K. G. Vollbrecht, D. Poulin, F. Verstraete, “Quantum Metropolis Sampling”, arXiv:0911.3635    Ref.TucQusann is R. R. Tucci, “Code Generator for Quantum Simulated Annealing”, arXiv:0908.1633    Ref.TucOrApprox is R. R. Tucci, “Oracular Approximation of Quantum Multiplexors and Diagonal Unitary Matrices”, arXiv:0901.3851    Ref.TucExact is R. R. Tucci, “Quantum Compiling with Approximation of Multiplexors”, arXiv:quant-ph/0412072    Ref.Kit is A. Yu. Kitaev, “Quantum measurements and the Abelian Stabilizer Problem”, quant-ph/9511026    Ref.TucZ is R. R. Tucci “Use of Quantum Sampling to Calculate Mean Values of Observables and Partition Function of a Quantum System”, arXiv:0912.4402    Ref.TucQOA is R. R. Tucci, “QOperAv, a Code Generator for Generating Quantum Circuits for Evaluating Certain Quantum Operator Averages”, arXiv:1010.4926    Ref.WikiWBugs is http://en.wikipedia.org/wiki/WinBugs    Ref.TucQuibbs is R. R. Tucci “Quibbs, a Code Generator for Quantum Gibbs Sampling”, arXiv:1004.2205
This invention deals with quantum computing. A quantum computer is an array of quantum bits (qubits) together with some hardware for manipulating those qubits. Quantum computers with several hundred qubits have not been built yet. However, once they are built, it is expected that they will perform certain calculations much faster that classical computers. A quantum computer follows a sequence of elementary operations. The operations are elementary in the sense that they act on only a few qubits (usually 1, 2 or 3) at a time. Henceforth, we will sometimes refer to sequences as products and to operations as operators, matrices, instructions, steps or gates. Furthermore, we will abbreviate the phrase “sequence of elementary operations” by “SEO” SEOs for quantum computers are often represented by quantum circuits. In the quantum computing literature, the term “quantum algorithm” usually means a SEO for quantum computers for performing a desired calculation. Some quantum algorithms have become standard, such as those due to Deutsch-Jozsa, Shor and Grover. One can find on the Internet many excellent expositions on quantum computing.
The quantum circuits that form part of this invention resemble those proposed prior to this invention in Ref.Har. Most of Ref.Har is preoccupied with encoding the solution of a system of linear equations into the amplitude of a quantum state. Only at the end (just before Appendix A, on page 5 of Version 3 of Ref.Har) do we find the following statement:                “Perhaps the most far-reaching generalization of the matrix inversion algorithm is not to invert matrices at all! Instead, it can compute ƒ(A)|b for any computable ƒ. Depending on the degree of nonlinearity of ƒ, non-trivial tradeoffs between accuracy and efficiency arise. Some variants of this idea are considered in [4, 12, 20].”To date, the authors of Ref.Har have not published in arXiv any follow-up papers developing further the idea expressed in the above quote.        
The following are some novel features of this invention over Ref.Har.                1. (different use) This invention is not used for solving systems of linear equations, so most of Ref.Har is irrelevant to this patent.        2. (lacks important details) The above quote from Ref.Har lacks important details. For example, it does not specify the nature of |b or how it should be created, or what types of expected values would be of particular interest and why.        3. (no V) The circuit 201 of FIG. 2 starts the atom qubits in a tensor product state |x and applies a circuit V to them. The circuit of Ref.Har has no operator that is a clear counterpart to V. Adding an operator V might seem trivial, but it is of much practical utility, for instance, in scenarios (a) and (b) of FIG. 6, where V equals a “basis-changer” unitary matrix UΩ, where Ω is a Hermitian operator whose expected value we seek.        4. (no multiplexor SEO) Ref.Har does not explain how the operator (what we call a “quantum multiplexor” in this patent) between times 3 and 4 in circuit 201 of FIG. 2 can be expanded into a SEO. By “SEO” we mean a sequence of elementary operations, and by “elementary operations” we mean operations that act on a few (usually 1, 2 or 3) qubits. In comparison, this invention explains very explicitly how to expand multiplexors into a SEO. In fact, this patent includes source code for a computer application called Multiplexor Expander that can expand multiplexors into a SEO in two different ways: an exact expansion and an oracular approximation expansion. The computer application Multiplexor Expander is explained in Ref.QuSann. The theoretical underpinnings of the oracular approximation expansion are explained in Ref.TucOrApprox. There are many possible ways of expanding a quantum multiplexor into an exact SEO. The type of exact expansion that the application Multiplexor Expander gives is explained in Ref.TucExact. This type of exact expansion is notable because it uses a low number of elementary operations compared with other possible exact expansions. It uses only 1-qubit and 2-qubit elementary operations, and a number of 2-qubit operations less than 2c+1, where c is the number of controls of the multiplexor.        5. (no machine) Ref.Har presents its algorithm in a very abstract way, divorced from any machine or computer program to implement it. Ref.Har gives no instructions on how to automate its algorithm, nor does it mention the huge benefits of doing so. This invention, on the other hand, is all about automating quantum circuit generation. It's like the difference between drawing cartoons by hand, and writing computer software that can produce a Pixar movie. Surely those who created software automating cartoon drawing invented something new beyond what hand painters of cartoons did.        
References 4, 12, 20 mentioned in the above quote are Ref.Chi, Ref.Ley, and Ref.She. These references use circuits that are significantly different from those used in this invention, and their circuits are used with a different purpose in mind. Furthermore, just like Ref.Har, they do not give an explicit SEO expansion of quantum multiplexor operators.
As is common practice, we will refer to Z=tr(e−βH) for some real parameter β and a Hermitian operator H, as a partition function. Evaluating partition functions is of much interest in physics and chemistry. Prior to Ref.TucZ, various methods had been proposed for calculating partition functions using a quantum computer. The most notable work in this regard is Ref.Woc, Ref.Pou and Ref.Tem. The method of this invention for calculating partition functions is significantly different from the methods proposed in those references. Ref.Woc and Ref.Pou use a sequence of β values, whereas this invention doesn't. Ref.Pou and Ref.Tem propose building a state ρ=e−βH/Z, whereas this invention doesn't.
The inventor Tucci first published a description of this invention on Dec. 22, 2010, in Ref.TucZ. Later, he added further details in Ref.TucQOA.